package LearnAlgorithm.c_递归and查找排序;

import java.util.HashMap;

public class o乱序数组查找超过一半的数 {
	public static void main(String[] args) {
		//方法一：先排序，返回数组中值
		//原因，大于一半，那么中值必定为“超过一半的那个数”
		//O(N*logN)
		int[] arr = new int[] {9,7,9,8,9,6,9,4,9,5,9,9};
		long before = System.currentTimeMillis();
		quickSortThree(arr, 0, arr.length - 1);
		util.Util.duration(before);
		System.out.println(arr[arr.length >>> 1]);
		
		//方法二：hash统计
		int[] arr2 = new int[] {9,7,9,8,9,6,9,4,9,5,9,9};
		
		//方法三：顺序统计，直接找K
		//原因：在数组整体有序的条件下，“那个数”必定出现在数组中值
		//O(N)
		int[] arr3 = new int[] {9,7,9,8,9,6,9,4,9,5,9,9};
		long before3 = System.currentTimeMillis();
		int target3 = selectK(arr3, 0, arr.length - 1, arr.length >>> 1);
		util.Util.duration(before3);
		System.out.println(target3);
		System.out.println("--------");
		//方法四：不同的数，进行删除
		//O(N)
		int[] arr4 = new int[] {9,7,9,8,9,6,9,4,9,5,9,9};
		long before4 = System.currentTimeMillis();
		scanNotSameDelete(arr4);
		util.Util.duration(before4);
	}
	
	public static void scanNotSameDelete(int[] arr) {
		int candidate = arr[0];//定义第一个候选数，这里默认第一个元素是候选数
		int nTimes = 1;//定义候选数出现的次数
		for (int i = 1; i < arr.length; i++) {//扫描整个数组
			if (nTimes == 0) {//如果次数==零
				candidate = arr[i];//新的元素作为候选数
				nTimes = 1;//重置为1
				continue;//跳出这次循环
			}
			if (candidate == arr[i]) {//如果新的元素==candidate
				nTimes++;//次数+1
			} else {
				nTimes--;//否则-1
			}
		}
		System.out.println(candidate);
	}
	
	public static int selectKByindex(int[] arr, int p, int r, int k) {
		return selectK(arr, p, r, k - 1);
	}
	
	public static int selectK(int[] arr, int p, int r, int k) {//使用老师的递归算法思想，放弃了自己的那种思想
		if (p < r) {
			int[] q = partitionThree(arr, p, r);
			int locationLeft = q[0] - p + 1;
			int locationRight = q[1] - p + 1;
			if (locationLeft <= k && k <= locationRight) {
				return arr[q[0]];
			} else if (k < locationLeft) {
				return selectK(arr, p, q[0] - 1, k);
			} else {
				return selectK(arr, q[1] + 1, r, k - locationRight);
			}
//			if (q == 0 && q != k) {//考虑两种边界值
//				if (q + 1 == k) {
//					return arr[q + 1];
//				} else {
//					return -1;
//				}
//			} else if (q == r - 1 && q != k) {//考虑两种边界值
//				if (r == k) {
//					return arr[r];
//				} else {
//					return -1;
//				}
//			}
//			if (q[0] <= k && k <= q[1]) {
//				return arr[q[0]];
//			} else if (k < q[0]) {
//				return selectK(arr, p, q[0] - 1, k);
//			} else {
//				return selectK(arr, q[1] + 1, r, k);
//			}
		} else {
			return -1;
		}
	}
	
	public static void quickSort(int[] arr, int p, int r) {
		if (p < r) {
			if (r - p + 1 <= 8) {
				insertSort(arr, p, r);
			} else {
				int q = partition(arr, p, r);
				quickSort(arr, p, q - 1);
				quickSort(arr, q + 1, r);
			}
		}
	}
	
	public static void quickSortThree(int[] arr, int p, int r) {
		if (p < r) {
			if (r - p + 1 <= 8) {
				insertSort(arr, p, r);
			} else {
				int[] q = partitionThree(arr, p, r);
				quickSortThree(arr, p, q[0] - 1);
				quickSortThree(arr, q[1] + 1, r);
			}
		}
	}
	
	public static int partition(int[] arr, int p, int r) {
		int midIndex = getMedian(arr, p, r);
		int piovet = arr[midIndex];
		while (p <= r) {
			while (p <= r && arr[p] <= piovet) {
				p++;
			}
			while (p <= r && arr[r] > piovet) {
				r--;
			}
			if (p < r) {
				swap(arr, p, r);
			}
		}
		return r;
	}
	
	//三分法不适合自己想的那一种“中值不换位置”的算法思想
	//因为等于中值的相同值是要看做“一块区域”
	//在数组整体有限的“长度”下，定死一块区域很傻
	//这块不灵活的区域会出很多问题：
	//假设相等值都在mid左侧，如果mid后面的值都小于piovet，需要被交换到前面去
	//然而前面有很多的相等值占据了位置，这不就出大问题了么
	public static int[] partitionThree(int[] arr, int p, int r) {
		int e = p + 1;
		int sp = p + 1;
		int bigger = r;
		int midIndex = getMedian(arr, p, r);
		swap(arr, p, midIndex);
		int piovet = arr[p];
		int[] equalNumber = new int[2];
		while (sp <= bigger) {
			while (sp <= bigger && arr[sp] <= piovet) {
				if (arr[sp] < piovet && sp == e) {
					sp++;
					e++;
				} else if (arr[sp] < piovet && sp != e) {
					swap(arr, e, sp);
					sp++;
					e++;
				} else {
					sp++;
				}
			}
			while (sp <= bigger && arr[bigger] > piovet) {
				bigger--;
			}
			if (sp < bigger) {
				swap(arr, sp, bigger);
			}
		}
		swap(arr, p, e - 1);
		equalNumber[0] = e - 1;
		equalNumber[1] = bigger;
		return equalNumber;
	}
	
	public static int getMedian(int[] arr, int p, int r) {
		int size = r - p + 1;
		int groupSize = (size % 5 == 0) ? (size / 5) : ((size / 5) + 1);
		int indexOfMedians = 0;
		int[] medians = new int[groupSize];
		HashMap<Integer, Integer> medainsOfValueAndIndex = new HashMap<Integer, Integer>();
		for (int i = 0; i < groupSize; i++) {
			if (i == groupSize - 1) {
				insertSort(arr, p + (i * 5), r);
				medians[indexOfMedians++] = arr[(p + (i * 5) + r) >>> 1];
				medainsOfValueAndIndex.put(arr[(p + (i * 5) + r) >>> 1], (p + (i * 5) + r) >>> 1);
			} else {
				insertSort(arr, p + (i * 5), p + (i * 5) + 4);
				medians[indexOfMedians++] = arr[p + (i * 5) + 2];
				medainsOfValueAndIndex.put(arr[p + (i * 5) + 2], p + (i * 5) + 2);
			}
		}
		insertSort(medians, 0, groupSize - 1);
		return medainsOfValueAndIndex.get(medians[(groupSize - 1) >>> 1]);
	}
	
	public static void insertSort(int[] arr, int p, int r) {
		int before_i = 0;
		int value_i = 0;
		for (int i = p + 1; i <= r; i++) {
			before_i = i - 1;
			value_i = arr[i];
			while (before_i > p - 1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i--];
			}
			arr[before_i + 1] = value_i;
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
